#include <stdio.h>
#include <string.h>
#include <glib/garray.h>
#include <glib.h>

#include "g_path_ext.h"

#define G_PARENT_DIR_STR     ".."
#define G_CURRENT_DIR_STR    "."

static gboolean
compare_substring(const gchar *a_begin,const gchar *a_end,const gchar *b)
{
  const gchar *a;

  a = a_begin;
  while(a != a_end && *b)
    {
      if(*a != *b)
        return FALSE;

      a++;
      b++;
    }

  /* Both strings should be past their last character. */
  return a == a_end && *b == '\0';
}

static gboolean
compare_substrings(const gchar *a_begin,const gchar *a_end,
  const gchar *b_begin,const gchar *b_end)
{
  const gchar *a;
  const gchar *b;

  a = a_begin;
  b = b_begin;
  while(a != a_end && b != b_end)
    {
      if(*a != *b)
        return FALSE;

      a++;
      b++;
    }

  /* Both strings should be past their last character. */
  return a == a_end && b == b_end;
}

typedef struct _PathElement	PathElement;
struct _PathElement
{
  const gchar *begin;
  const gchar *end;
};

static GArray*
split_into_elements(const gchar *path_begin,const gchar *path_end)
{
  PathElement cur_element;
  const gchar *c;
  GArray *ret;

  ret = g_array_new(TRUE,FALSE,sizeof(PathElement));

  c = path_begin;

  /* Skip any initial dir separators. */
  while(c != path_end && G_IS_DIR_SEPARATOR(*c))
    {
      c++;
    }

  if(*c == '\0')
    {
      /* return an empty array (don't return NULL, as we don't consider it an error) */
      return ret;
    }

  cur_element.begin = c;
  while(c != path_end)
    {
      if(G_IS_DIR_SEPARATOR(*c))
        {
          cur_element.end = c;
          g_array_append_val(ret,cur_element);

          c++;

          /* Skip any subsequent dir separator chars, as we don't want empty elements. */
          while(c != path_end && G_IS_DIR_SEPARATOR(*c))
            {
              c++;
            }
          cur_element.begin = c;
        }
      else
        c++;
    }

  /* If cur_element.begin isn't pointing to the end of the string
   * (which happens in case the last character was a /),
   * we add the part from the current element's begin, up to the end of the
   * string, as the last element. */
  if(cur_element.begin != path_end)
    {
      cur_element.end = c;
      g_array_append_val(ret,cur_element);
    }

  return ret;
}

static inline gboolean
compare_path_element(PathElement *element,const gchar *comparand)
{
  return compare_substring(element->begin,element->end,comparand);
}

static inline gboolean
compare_path_elements(PathElement *a,PathElement *b)
{
  return compare_substrings(a->begin,a->end,b->begin,b->end);
}

/* basically, just skips .'s, and pops one element for each ..
 * returns TRUE if successful, FALSE if it failed.*/
static gboolean
canonicalize_path_elements(GArray *elements,int start_index)
{
  PathElement *write_ptr;
  PathElement *read_ptr;
  int new_size = start_index;

  read_ptr = write_ptr = &g_array_index(elements,PathElement,start_index);

  while(read_ptr->begin)
    {
      if(compare_path_element(read_ptr,G_PARENT_DIR_STR))
        {
          /* it's a '..', so we have to pop one element from the resulting array */

          if(new_size == 0)
            {
              /* Can't canonicalize, because there are more ..'s in the path
               * than actual directories. */
              return FALSE;
            }

          write_ptr--;
          new_size--;
        }
      else if(compare_path_element(read_ptr,G_CURRENT_DIR_STR))
        {
          /* It's a '.', which we should just skip. */
        }
      else
        {
          *(write_ptr++) = *read_ptr;
          new_size++;
        }

      read_ptr++;
    }

  g_array_set_size(elements,new_size);

  return TRUE;
}

static gchar*
construct_path_from_elements(GArray *elements,gboolean leading_separator)
{
  gchar *ret;
  gchar *write_ptr;
  PathElement *cur_element;
  int ret_length;

  if(elements->len == 0)
    {
      ret = g_malloc(1);
      ret[0] = 0;
      return ret;
    }

  ret_length = leading_separator ? 1 : 0;
  for(cur_element = &g_array_index(elements,PathElement,0);
    cur_element->begin;cur_element++)
    {
      ret_length += (int)(cur_element->end - cur_element->begin);
      ret_length++; /* For the path separator. */
    }

  ret = (gchar*)g_malloc(ret_length + 1);
  if(!ret)
    return NULL;

  write_ptr = ret;

  if(leading_separator)
    *(write_ptr++) = G_DIR_SEPARATOR;

  cur_element = &g_array_index(elements,PathElement,0);
  while(1)
    {
      const gchar *read_ptr;
      for(read_ptr = cur_element->begin;read_ptr != cur_element->end;read_ptr++)
        *(write_ptr++) = *(read_ptr);

      cur_element++;
      if(cur_element->begin == 0)
        break;

      *(write_ptr++) = G_DIR_SEPARATOR;
    }

  *write_ptr = 0;  /* Null terminator */

  return ret;
}

gchar*
g_path_get_relative_path(const gchar *full_path,const gchar *base_path)
{
  GArray *full_path_elements = NULL;
  GArray *base_path_elements = NULL;
  GArray *result_elements = NULL;
  gchar *ret;
  PathElement *cur_full_path_element;
  PathElement *cur_base_path_element;

  g_return_val_if_fail(g_path_is_absolute(full_path),0);
  g_return_val_if_fail(g_path_is_absolute(base_path),0);

  full_path_elements = split_into_elements(full_path,full_path + strlen(full_path));
  if(!full_path_elements)
    goto error;
  if(!canonicalize_path_elements(full_path_elements,0))
    goto error;

  base_path_elements = split_into_elements(base_path,base_path + strlen(base_path));
  if(!base_path_elements)
    goto error;
  if(!canonicalize_path_elements(base_path_elements,0))
    goto error;

  result_elements = g_array_new(TRUE,FALSE,sizeof(PathElement));
  if(!result_elements)
    goto error;

  cur_full_path_element = &g_array_index(full_path_elements,PathElement,0);
  cur_base_path_element = &g_array_index(base_path_elements,PathElement,0);

  /* Process the elements both paths have in common. */
  while(cur_full_path_element->begin &&
    cur_base_path_element->begin)
    {
      if(!compare_path_elements(cur_full_path_element,cur_base_path_element))
        {
          break;
        }

      cur_full_path_element++;
      cur_base_path_element++;
    }

  /* For each one of the remaining parts in base_path, we have to
   * add a .. to the output path. */
  while(cur_base_path_element->begin)
    {
      static const gchar one_up[] = G_PARENT_DIR_STR;
      PathElement cur_element;

      cur_element.begin = one_up;
      cur_element.end = one_up + strlen(one_up);
      g_array_append_val(result_elements,cur_element);

      cur_base_path_element++;
    }

  /* Append the remaining part */
  while(cur_full_path_element->begin)
    {
      g_array_append_val(result_elements,*cur_full_path_element);

      cur_full_path_element++;
    }

  ret = construct_path_from_elements(result_elements,FALSE);

  g_array_free(full_path_elements,TRUE);
  g_array_free(base_path_elements,TRUE);
  g_array_free(result_elements,TRUE);

  return ret;

error:
  g_array_free(full_path_elements,TRUE);
  g_array_free(base_path_elements,TRUE);
  g_array_free(result_elements,TRUE);
  return NULL;
}

gchar*
g_path_canonicalize_path(const gchar *in_path)
{
  return g_path_canonicalize_path_full(in_path,CPF_NATIVE_PATH);
}

gchar*
g_path_canonicalize_path_full(const gchar *in_path,int flags)
{
  const gchar *in_path_end = 0;
  GArray *elements = 0;
  gchar *ret = 0;
  int format;

  typedef enum
  {
    RELATIVE,
    FROM_ROOT,
    WITH_DRIVE,
  } PathOrigin;
  PathOrigin origin;

  format = flags & CPF_FORMAT_MASK;
  if(format == CPF_NATIVE_PATH)
    {
#ifdef WIN32
      format = CPF_WINDOWS_PATH;
#else
      format = CPF_UNIX_PATH;
#endif
    }

  if(format == CPF_UNIX_PATH)
    {
      origin = G_IS_DIR_SEPARATOR(in_path[0]) ? FROM_ROOT : RELATIVE;
    }
  else
    {
      g_assert(format == CPF_WINDOWS_PATH);

      if(G_IS_DIR_SEPARATOR(in_path[0]))
        origin = FROM_ROOT;
      else if(in_path[0] != '0' && in_path[1] == ':' && G_IS_DIR_SEPARATOR(in_path[2]))
        origin = WITH_DRIVE;
      else
        origin = RELATIVE;
    }

  in_path_end = in_path + strlen(in_path);
  elements = split_into_elements(in_path,in_path_end);

  if(!canonicalize_path_elements(elements,origin == WITH_DRIVE ? 1 : 0))
    goto error;

  ret = construct_path_from_elements(elements,origin == FROM_ROOT);
  if(!ret)
    goto error;

  g_array_free(elements,TRUE);

  return ret;

error:
  g_array_free(elements,TRUE);
  g_free(ret);
  return 0;
}

GPtrArray*
g_path_split_into_elements(const gchar *full)
{
  /* the elements array contains instances of the PathElement struct.
  the ret array contains strings (gchar*) */
  GArray *elements = 0;
  GPtrArray *ret = 0;
  size_t i;
  PathElement *cur_elem;
  size_t cur_elem_len;
  gchar *cur_elem_str;

  elements = split_into_elements(full,full + strlen(full));

  ret = g_ptr_array_sized_new(elements->len);
  for(i = 0;i < elements->len;i++)
    {
      cur_elem = &g_array_index(elements,PathElement,i);
      cur_elem_len = cur_elem->end - cur_elem->begin;

      cur_elem_str = (gchar*)g_malloc((gulong)cur_elem_len + 1);
      if(!cur_elem_str)
        goto error;

      memcpy(cur_elem_str,cur_elem->begin,cur_elem_len);
      cur_elem_str[cur_elem_len] = 0;

      g_ptr_array_add(ret,cur_elem_str);
    }

  g_array_free(elements,TRUE);

  return ret;

error:
  g_array_free(elements,TRUE);

  for(i = 0;i < (size_t)ret->len;i++)
    g_free(g_ptr_array_index(ret,i));
  g_ptr_array_free(ret,TRUE);
  return 0;
}

